package 动态规划;


import java.util.HashMap;

public class Solution70 {

    public static void main(String[] args) {
        System.out.println(climbStairs(3));
        System.out.println(dp(3));
    }

    public static int climbStairs(int n) {
        HashMap<Integer, Integer> map = new HashMap<>();
        return process(n, map);
    }

    //剩余步，走1还是2
    //返回走的走法
    public static int process(int n, HashMap<Integer, Integer> map) {

        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 1;
        }
        if (map.get(n) != null) {
            return map.get(n);
        }
        int p1 = process(n - 1, map);
        int p2 = process(n - 2, map);
        int ans = p1 + p2;
        map.put(n, ans);
        return ans;
    }

    //剩余步，走1还是2
    //返回走的走法
    public static int dp(int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }


}
